The present invention relates to data communications, specifically to an apparatus and method for allocating bits among carrier tone subchannels (bins) in a discrete multitone modulation (DMT) communication system. The present invention allows DMT communication to proceed at a data rate via communication equipment which is less complicated, less costly, and more efficient than prior DMT communication devices.
Data transmission modulation schemes are broken into many categories, the two major of which are single carrier modulation and multicarrier modulation. Single carrier modulation employs the use of a single frequency upon which data is modulated. For example, a single carrier modem might use a 2 KHz carrier and quadrature amplitude modulation (QAM) or phase shift keying (PSK) modulation to xe2x80x9csuperimposexe2x80x9d the data on the carrier. Although used in many applications and environments, single carrier modulation modems, such as V.34 modems, are often used on voiceband systems such as POTS lines (plain old telephone system). Further, bit allocation among carrier tones is not an issue in single carrier modulation systems since only one carrier tone is used. As such, the invention is not directed to single carrier systems.
The other category of modulation transmission techniques is multicarrier modulation. In multicarrier modulation communications, the transmission channel is partitioned into a number of narrowband subchannels. These narrowband transmission subchannels typically correspond to a series of contiguous frequency bands in which each subchannel uses a distinct carrier frequency. This distinct carrier frequency is also referred to as a xe2x80x9ctonexe2x80x9d, and the subchannel is referred to as a xe2x80x9cbinxe2x80x9d. The capacity of the entire transmission channel is the sum of the capacities of each individual subchannel. The method for assigning data information and energy to each of the subchannels in a multichannel transmission environment is called xe2x80x9cloadingxe2x80x9d. The distribution of data information among the channels is referred to as xe2x80x9cbit allocationxe2x80x9d.
Multicarrier modulation techniques for data communication are not new, and have been known and used for the past 50 years. However, prior to the proliferation of digital communication technologies and efficient methods for digital signal processing, multicarrier modulated communication systems often relied on a group of modems with differing carrier frequencies whose signals were added together to form a composite signal. As shown in FIG. 1, a data stream would enter a serial to parallel signal splitter 2 whose output would feed a plurality of modems 4. The modems would each be set to modulate at a different carrier frequency. The analog output of each modem would be added together and transmitted along the communication channel 8. The composite signal would be separated and demodulated at the receiving end via a complementary set of equipment.
This technique required multiple modems, was not reliable and did not take into account the different operating and performance characteristics of each individual carrier frequency. This resulted in an inefficient use of the communication channel resources. For example, in a typical communication environment, signals with higher frequencies attenuate quicker and are more subject to noise than signals at low frequencies. Thus, it was possible that a subchannel with a high signal-to-noise ratio could be under utilized, while a subchannel with a low signal-to-noise ratio could be over utilized resulting in an unnecessary degradation in overall transmission channel performance.
Subsequent DMT multicarrier modulation equipment made use of digital signal processing techniques including Fast Fourier Transforms and Inverse Fast Fourier Transforms. Digital signal processing allowed a single DMT communication device to be used to modulate all subchannels, thereby improving reliability and lowering the cost of communications. These devices, however, were still constrained by the limitations of their predecessors, namely, inefficient use of the communication channel resources.
A preferred approach is to load each subchannel based on the individual transmission characteristics of that subchannel. Better subchannels, should carry more information than poorer quality subchannels. This allows an efficient use of the communication channel resources.
Transmission channels are typically characterized by the channel""s margin, signal-to-noise ratio gap (hereinafter SNR gap), and capacity. All are related concepts. The margin is the amount of additional signal-to-noise ratio in excess of the minimum required to achieve a given performance level for a particular type of modulation scheme with a particular SNR gap. The SNR gap is a function of a chosen probability of transmission error and the modulation and coding techniques. The SNR gap measures the inefficiency of the transmission method with respect to the best possible performance, assuming an additive white Gaussian noise channel. The SNR gap is often constant over a wide range of transmission rates which may be transmitted by the particular modulation coding technique. The channel capacity refers to the maximum data rate capable of being transmitted on a particular channel. The optimum line coding technique has a SNR gap of zero dB. Although such an optimum line code requires infinite decoding/encoding delay and is infinitely complex, it has become practical at typical Digital Subscriber Line (DSL) speeds to implement modulation methods to achieve SNR gaps as low as 1-2 dB. Therefore, one factor to be considered during the bit allocation process is the transmission quality of each subchannel, in order to maximize the bit allocation for each subchannel.
Another factor to be considered during the bit allocation process is gain scaling. Gain scaling allows an individual subchannel to be amplified or attenuated based on a set of parameters. Certain DSL technologies and standards such as the Asymmetric Digital Subscriber Line (ADSL) T1.413 standard specify a scaling range, such as xc2x12.5 dB, subject to a maximum total energy level for the entire channel. However, these standards do not specify how to implement the gain scaling factor.
Bit allocation in a discrete multitone transmission environment is a well-studied problem, relating to the development of a number of different bit allocation algorithms. Optimum bit allocation can be achieved using the well-known xe2x80x9cwater-fillingxe2x80x9d algorithm. However, there are two major drawbacks with xe2x80x9cwater-fillingxe2x80x9d. First, the resulting calculated bit distribution is not necessarily a set of integers. This may result in complications during implementation. Second, the xe2x80x9cwater-fillingxe2x80x9d algorithm maximizes the aggregate bit rate for a given margin and bit error rate. However, maximizing the margin at a given bit error rate and a given bit rate is desirable in many applications.
The loading goal of bit-loading is generally classified as either rate-adaptive loading or margin-adaptive loading. In rate-adaptive loading, the data rate is maximized subject to the constraint of fixed total power. In margin-adaptive loading, the goal is to maximize the margin at a fixed data rate.
There are at least two popular strategies employed to try to achieve these goals. The first, Chow""s algorithms, suggests an on/off energy distribution, and only approximately solve the problems associated with achieving the rate-adaptive and margin-adaptive loading goals. The second category is Greedy algorithms. This well-known class of algorithms can solve the loading problems exactly. For example, the Hughes-Hartog and Campello algorithms belong to the family of Greedy algorithms. Greedy algorithms work to allocate bits to the subchannels in an incremental way such that a subchannel is always chosen for the next bit to be allocated according to the least cost in energy. In other words, the best subchannel gets the first bit, and a table of incremental next energies for the next bit must be computed and the process continued until all bits have been allocated in the case of margin-adaptive loading, and until there is no more energy available in the case of rate-adaptive loading.
Although these algorithms can solve the bit-loading problem, there are a number of significant drawbacks associated with their implementation. First, the computational load required to implement these algorithms can be very large. This can significantly drive up the cost of implementation in modem hardware, due to computational complexity. The computational load in the prior art algorithms typically arises because (1) the algorithms require global operations such as sorting, finding maximum or minimum values of a set of numbers, finding geometric means, etc. over all subchannels; (2) the algorithms require iterative processing; and (3) the algorithms may require that logarithmic operations be performed. Regarding (1), because the number of subchannels can be quite large (over 100 in many cases), performing global operations can result in hefty processing and storage requirements.
In addition, the water-filling, Chow""s and Greedy algorithms do not take gain scaling into account as part of their bit-loading calculations. However, gain scaling must be done in order to have the same bit error rate with an integer number of bits as opposed to a result which provides the same bit error rate but a non-integer number of bits. In other words, gain scaling is required in order to round the resultant bit allocation for a subchannel to the next highest or lowest integer value when that number is calculated to achieve a particular bit error rate.
The relation between the number of bits b in a subchannel i and the signal-to-noise ratio (SNR) in that subchannel is:                               b          i                =                              log            2                    ⁡                      (                          1              +                                                SNR                  i                                γ                                      )                                              (                  Equation          ⁢                      xe2x80x83                    ⁢          1                )            
where xcex3 is the SNR gap. The detail behind the derivation of this equation is described below. Recall that the SNR gap depends on the type of modulation and coding used in a transmitter as well as the target bit error rate (BER). This same expression can be rewritten in order to express the SNR required to achieve a particular number of bits per subchannel. Because this expression must hold after bit allocation has been completed, gain scaling should be done at the transmitter to ensure that the received SNR in the i subchannel corresponds to bi bits in that subchannel. In addition, certain transmission standards, such as the ADSL standards, specify a spectrum mask for the transmitted signal which specifies the minimum and maximum amount of gain scaling allowed in a given bin. Adding the constraint of limiting gain scaling to the above algorithms requires that they be modified further, thereby further increasing the complexity of calculations and modem hardware requirements. The prior art algorithms also do not support a bit allocation method which allows different subchannels to operate at different bit error rates or margins.
It is desirable to use a bit allocation method and apparatus which accurately determine bit allocations for a large number of subchannels, and which takes into account gain scaling and a gain scaling cap.
It is also desirable to have a bit allocation method which does not require that the transmission hardware and software perform any sorting or complex mathematical operations. It is further desirable to have a method which can allocate bits to subchannels based on a desired bit error rate, and further to be able to allow subchannels to operate at different bit error rates.
An object of the invention is to provide a method of allocating bits to a plurality of transmission subchannels in a communication system in which a storing step stores at least one bits to signal-to-noise ratio table in a memory. A determining step determines a bit allocation value and a gain scaling factor for each of the plurality of transmission subchannels in accordance with the at least one stored bits to signal-to-noise ratio table.
In accordance with this method, the stored table is comprised of a plurality of minimum signal-to-noise ratio values and a corresponding plurality of respective bit values, the minimum signal-to-noise ratio values being determined in accordance with a maximum allowable gain scaling factor, wherein the signal-to-noise ratio values also correspond to the plurality of respective bit values.
It is another object of the present invention to provide a method of allocating bits to a plurality of transmission subchannels in a communication system, in which a measuring step measures a signal-to-noise ratio for each of the plurality of transmission subchannels. An adjusting step adjusts the measured signal-to-noise ratio in accordance with an SNR-margin and a coding gain. A generating step generates a plurality of signal-to-noise ratio difference values. A selection step selects a bit allocation value for each of the plurality of transmission subchannels, the bit allocation value corresponding to one of the plurality of signal-to-noise ratio difference values. A determining step determines a gain scaling factor for each of the plurality of transmission subchannels, and a storing step stores each of the bit allocation values and the gain scaling factors in one or more data structures.
It is yet another object of the present invention to provide a data communication apparatus for allocating bits to a plurality of transmission subchannels in a communication system, in which there is a memory for storing at least one bits to signal-to-noise ratio table. A processing unit determines a bit allocation value and a gain scaling factor for each of the plurality of transmission subchannels in accordance with the at least one stored bits to signal-to-noise ratio table.
Another object of the present invention is to provide a data communication apparatus for allocating bits to a plurality of transmission subchannels in a communication system, in which there is a memory and a processing unit. The processing unit controls functions which measure a signal-to-noise ratio for each of the plurality of transmission subchannels, adjust the measured signal-to-noise ratio in accordance with an SNR-margin and a coding gain, generate a plurality of signal-to-noise ratio difference values, select a bit allocation value for each of the plurality of transmission subchannels, the bit allocation value corresponding to one of the plurality of signal-to-noise ratio difference values, determine a gain scaling factor for each of the plurality of transmission subchannels, and store each of the bit allocation values and the gain scaling factors as one or more data structures in the memory.
Other features and advantages of the present invention will become apparent from the following description of the invention which refers to the accompanying drawings.